package com.example.demo2;

import java.util.ArrayList;
import java.util.List;

public class Test2 {
    public static void main(String[] args) {
        /*
        需求：
        目前有100名囚犯，每个囚犯的编号是1-200之间的随机数。现在要求依次随机生成100名囚犯的编号（要求这些囚犯的编号是不能重复的），
        然后让他们依次站成一排。(注：位置是从1开始计数的)，接下来，国王命令手下先干掉全部奇数位置处的人。剩下的人，又从新按位置1开始，
        再次干掉全部奇数位置处的人，依此类推，直到最后剩下一个人为止，剩下的这个人为幸存者。
         */
        // 思路分析：使用面向对象编程：创建对象代表一个一个的囚犯(第一次的位置和它的编号)

        // 1.创建一个ArrayList集合存放100个囚犯对象
        List<Prisoner> prisoners = new ArrayList<>();
        for (int i = 1; i <= 100; i++) {
            // 生成1-200之间的随机数
            int num = (int) (Math.random() * 200 + 1);
            // 判断这个编号是否重复了
            if (isRepeat(prisoners, num)) {
                // 重复了，重新生成
                i--; // 让循环回退一步
                continue; // 跳过本次循环
            }
            Prisoner p = new Prisoner(num, i);
            prisoners.add(p);
        }
        System.out.println(prisoners);

        // 2.干掉集合中的所有奇数位置的囚犯
        // prisoners = 【p1, p2, p3, p4, p5 , p6】
        //                   1       3        5
        // 不断缩小囚犯集合，直到只剩下最后一名囚犯
        while (true) {
            // 定义一个新集合存储本轮干掉后剩下的囚犯
            List<Prisoner> lastPrisoners = new ArrayList<>();
            // 遍历当前囚犯集合，每次跳过一个囚犯，将存活的囚犯添加到新集合中
            for (int i = 1; i < prisoners.size(); i += 2) {
                lastPrisoners.add(prisoners.get(i));
            }
            // 如果新集合中只剩下一个囚犯，则输出这个囚犯的编号和最初的位置，然后结束循环
            if (lastPrisoners.size() == 1) {
                Prisoner prisoner = lastPrisoners.get(0);
                System.out.println("最后剩下的囚犯的编号：" + prisoner.getId() + ", 最开始的位置：" + prisoner.getFirstLocation());
                break;
            }
            // 将新集合赋值给当前囚犯集合，进行下一轮淘汰
            prisoners = lastPrisoners;
        }
    }

    /**
     * 判断编号是否重复
     * @param prisoners 存储囚犯集合
     * @param num 编号
     * @return 如果返回true，说明编号重复，返回false，说明编号不重复
     */
    public static boolean isRepeat(List<Prisoner> prisoners, int num) {
        for (Prisoner p : prisoners) {
            if (p.getId() == num) {
                return true;
            }
        }
        return false;
    }
}
